# 分隔链表： https://leetcode-cn.com/problems/split-linked-list-in-parts/

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 自己的想法
class Solution:
    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:
        """
            我的想法
            1. 首先记录一下链表的长度 n
            2. 因为是前面的长度必须大于等于后面的长度，且长度差不超过1. 所以 n // k, 求出平均每个多长
            3. 剩余的长度，优先从前面加。 
        """
        # 1. 求链表长度, 从 0 开始，因为 head 可能是 None
        n = 0
        cur = head
        while cur: 
            cur = cur.next
            n += 1
        
        # 2. avg
        avgLength = n // k
        # 剩余
        rm = n % k

        # 3. 
        rst = []
        p = head
        # count的用来计数， 前 rm次，长度要加1
        count = 0
        # 分为k段，计数
        countK = 0
        # 原本是写为 while p or countK < k, 后来发现，只需要规定 分段数就可以，按照既定计划，不会出现 p为None还继续的情况
        while countK < k:
            # 注意，这里需要设立首元结点，否则当 [1,2,3] 5， 这种情况，平分的为 0 ，处理不了
            dumpy = ListNode(0) 
            h = dumpy
            for i in range(avgLength):
                h.next = p
                h = p
                p = p.next
            
            if count < rm:
                h.next = p
                h = p
                p = p.next
                count += 1

            rst.append(dumpy.next)
            h.next = None
            countK += 1
        
        return rst


# 可以优化代码，中间有比较冗余
# for 循环这里用的太秒了！！ 简洁，高效，便捷！
class Solution:
    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:
        """
            我的想法
            1. 首先记录一下链表的长度 n
            2. 因为是前面的长度必须大于等于后面的长度，且长度差不超过1. 所以 n // k, 求出平均每个多长
            3. 剩余的长度，优先从前面加。 
        """
        # 1. 求链表长度, 从 0 开始，因为 head 可能是 None
        n = 0
        cur = head
        while cur: 
            cur = cur.next
            n += 1
        
        # 2. avg
        avgLength = n // k
        # 剩余
        rm = n % k

        # 3. 
        rst = []
        p = head
        # 使用for 循环：
        for i in range(k):
            realLength = avgLength + 1 if i < rm else avgLength
            # 注意，这里需要设立首元结点，否则当 [1,2,3] 5， 这种情况，平分的为 0 ，处理不了
            dumpy = ListNode(0) 
            h = dumpy
            for i in range(realLength):
                h.next = p
                h = p
                p = p.next

            rst.append(dumpy.next)
            h.next = None
        
        return rst